package main

import (
	"flag"
	"fmt"
	"log"
	"os"
	"syscall"
	"time"
)

const (
	LenGrid    = 9                 /* 数独都有9行9列格子 */
	Length     = LenGrid * LenGrid /* 数独有81个元素 */
	NineDance  = 9 * Length        /* 81*9 创建出9个舞蹈链,分别代表填入的数字 */
	FourDance  = 4 * Length        /* 81*4 约束条件 */
	MinInitial = 1000000000        /* 最小min的初值 */
)

type Node struct {
	r, c  int /* 标识第r行,第c列 */
	up    *Node
	down  *Node
	left  *Node
	right *Node
}

var (
	SudokuData [Length + 1]int                /* 保存数独数据 */
	Mem1       [Length + 1]int                /* 保存数独结果1 */
	Mem2       [Length + 1]int                /* 保存数独结果2 */
	Mem        = &Mem1                        /* 用mem操作2个结果内的值 */
	Cnt        [FourDance + 1]int             /* 0-324  用于记录0-324列,这一列有多少个结点 */
	SCnt       = 0                            /* 记录数独结果个数,本程序最多找到2个就退出 */
	Head       Node                           /* 头结点 */
	All        [NineDance*FourDance + 99]Node /* 0-236294  构建729*324+99列的舞蹈链 */
	AllCnt     int                            /* 舞蹈链的游标 */
	Row        [NineDance]Node                /* 0-728  构建729列的舞蹈链，用于1-9的填入，每个数字用81列来表示 */
	Col        [FourDance]Node                /* 0-323  构建324列的舞蹈链，用于满足4个约束条件 */
)

func init() {
	fr := flag.String("f", "Sudoku.txt", "input data file!")
	flag.Parse()

	byt, err := os.ReadFile(*fr)
	if err != nil {
		log.Fatal(err.Error())
	}

	var cnt = 0
	for _, v := range byt {
		if v >= '0' && v <= '9' {
			if cnt < Length { /* 数独只有81个元素 */
				SudokuData[cnt] = int(v - '0')
			}
			cnt++
		}
	}

	if cnt != Length { /* 无论如何只有81个数字输入 */
		log.Fatal("输入文件只能有81个数字!")
	}
	SudokuData[cnt] = MinInitial /* 标识结束符 */
	AllCnt = 1                   /* 舞蹈链从位置1开始 */

	Head.left = &Head  /* 头结点的左边是头结点 */
	Head.right = &Head /* 头结点的右边是头结点 */
	Head.up = &Head    /* 头结点的上面是头结点 */
	Head.down = &Head  /* 头结点的下面是头结点 */
	Head.r = NineDance /* 行数等于729 */
	Head.c = FourDance /* 列数等于324 */

	for cnt = 0; cnt < FourDance; cnt++ {
		Col[cnt].c = cnt          /* 324列舞蹈链 用0-323赋值给c */
		Col[cnt].r = NineDance    /* 把 729 赋给 r */
		Col[cnt].up = &Col[cnt]   /* 它的上面等于自己 */
		Col[cnt].down = &Col[cnt] /* 它的下面等于自己 */

		Col[cnt].left = &Head           /* 它的左边等于头结点 */
		Col[cnt].right = Head.right     /* 它的右边等于头结点的右边 */
		Col[cnt].left.right = &Col[cnt] /* 它的左边的右边等于自己 */
		Col[cnt].right.left = &Col[cnt] /* 它的右边的左边等于自己 */
	}

	for cnt = 0; cnt < NineDance; cnt++ {
		Row[cnt].r = cnt       /* 729行舞蹈链，行数等于i */
		Row[cnt].c = FourDance /* 列数等于324 */

		Row[cnt].left = &Row[cnt]  /* 它的左边等于自己 */
		Row[cnt].right = &Row[cnt] /* 它的右边等于自己 */

		/* 头结点下边行的编号从上到下是728到0 */
		Row[cnt].up = &Head          /* 它的上边等于头结点 */
		Row[cnt].down = Head.down    /* 它的下边等于头结点的下边 */
		Row[cnt].up.down = &Row[cnt] /* 它的上边的下边等于自己 */
		Row[cnt].down.up = &Row[cnt] /* 它的下边的上边等于自己 */
	}

	/* 访问所有行,数独舞蹈链中的第i行 表示 数独中的第r行第c列中填入数字val */
	for cnt = 0; cnt < NineDance; cnt++ {
		var (
			r   = cnt / 9 / 9 % 9 /* 0-80  r为0   81-161 r为1 …… 648-728 r为8    表示数独中的行    映射：舞蹈链行->数独行 */
			c   = cnt / 9 % 9     /* 0-8  c为0   9-17 c为1   18-26  c为2   ……   72-80为8  循环直至720-728为8  81个为一个周期   表示数独中的列  映射：舞蹈链行->数独列 */
			val = cnt%9 + 1       /* 0为1  1为2  2为3  ……  8为9   9个为一个周期   表示数字1-9   映射：舞蹈链行->1-9数字 */
		)
		if SudokuData[r*9+c] == 0 || SudokuData[r*9+c] == val { /* r表示第r行,c表示第c列，如果数独的第r行第c列是0-9 */
			/* 如果数独的第r行第c列是0号则它的所有行都建立舞蹈链结点 */
			/* 如果数独的第r行第c列是数字则它的指定行都建立舞蹈链结点 */
			Link(cnt, r*9+val-1)        /* 处理约束条件1：每个格子只能填一个数字    0-80列 */
			Link(cnt, Length+c*9+val-1) /* 处理约束条件2：每行1-9这9个数字只能填一个   81-161列 */
			tr := r / 3
			tc := c / 3
			Link(cnt, Length*2+(tr*3+tc)*9+val-1) /* 处理约束条件3：每列1-9的这9个数字都得填一遍 */
			Link(cnt, Length*3+r*9+c)             /* 处理约束条件4：每宫1-9的这9个数字都得填一遍 */
		}
	}

	/* 把728个行结点全部删除 */
	for cnt = 0; cnt < NineDance; cnt++ {
		Row[cnt].left.right = Row[cnt].right /* 每一行左边的右边等于行数的右边 */
		Row[cnt].right.left = Row[cnt].left  /* 每一行右边的左边等于行数的左边 */
	}
}

/**
* 主程序入口
* http://aperiodic.net/phil/scala/s-99/
* https://www.newdoku.com/zh/sudoku.php
* http://www.cnblogs.com/grenet/p/3145800.html 讲解舞蹈链
* http://www.cnblogs.com/grenet/p/3163550.html 讲解如何用舞蹈链解数独
**/
func main() {
	var tStart = time.Now() /* 开始时间 */
	Solve(1)
	var useTime = time.Since(tStart) /* 计算用时 */

	/* 下面打印数独,初始化数据和打印都不计入运算时间 */
	switch SCnt {
	case 2:
		PrintSudoku(1)
		PrintSudoku(2)
		fmt.Print("  2个或者多个解的数独")
	case 1:
		PrintSudoku(1)
		fmt.Print("  1个解的数独")
	default:
		fmt.Print("  此数独无解")
	}
	fmt.Println(",计算耗时:", useTime)
	_, _ = fmt.Scanln() /* 避免一闪而逝 */
}

/*Link
  用链表解释就是一直插在第一个结点，以前的结点右推。
  第r行,第c列
*/
func Link(r, c int) {
	Cnt[c]++          /* 第c列的结点增加了一个 */
	t := &All[AllCnt] /* 将指针指向下一个，就像线性表添加元素一样 */
	AllCnt++
	t.r = r /* t的行数等于r */
	t.c = c /* t的列数等于c */

	t.left = &Row[r]       /* t的左边等于第r行结点 */
	t.right = Row[r].right /* t的右边等于第r行结点的右边 */
	t.left.right = t       /* t的左边的右边等于t */
	t.right.left = t       /* t的右边的左边等于t */

	t.up = &Col[c]       /* t的上边等于第c列结点 */
	t.down = Col[c].down /* t的下边等于第c列下边 */
	t.up.down = t        /* t的上边的下边等于t */
	t.down.up = t        /* t的下边的上边等于t */
}

/*Remove
* 删除这列的结点和结点所在行的结点
**/
func Remove(c int) {
	var t, tt *Node
	/* 删除列结点 */
	Col[c].right.left = Col[c].left  /* 该列结点的右边的左边等于该列结点的左边 */
	Col[c].left.right = Col[c].right /* 该列结点的左边的右边等于该列结点的右边 */

	for t = Col[c].down; t != &Col[c]; t = t.down { /* 访问该列的所有结点 直到回到列结点 */
		for tt = t.right; tt != t; tt = tt.right { /* 访问该列所有结点所在的每一行 */
			Cnt[tt.c]-- /* 该列的结点减少一个 */

			/* 删除该结点所在行中的一个结点 */
			tt.up.down = tt.down /* 该结点的上边的下边等于该结点的下边 */
			tt.down.up = tt.up   /* 该结点的下边的上边等于该结点的上边 */
		}

		/* 删除该结点 */
		t.left.right = t.right /* t的左边的右边等于t的右边 */
		t.right.left = t.left  /* t的右边的左边等于t的左边 */
	}
}

/*Resume
* 恢复一个节点
**/
func Resume(c int) {
	var t, tt *Node
	/* 遍历该列结点 */
	for t = Col[c].down; t != &Col[c]; t = t.down {
		t.right.left = t /* 恢复t结点 */
		t.left.right = t /* 恢复t结点 */

		for tt = t.left; tt != t; tt = tt.left { /* 一直访问左边，直到回到t */
			Cnt[tt.c]++
			tt.down.up = tt
			tt.up.down = tt
		}
	}
	Col[c].left.right = &Col[c]
	Col[c].right.left = &Col[c]
}

/*Solve
* 计算数独
**/
func Solve(k int) {
	var (
		t, tt *Node
		min   = MinInitial
		tc    int
	)

	if Head.right == &Head { /* 得到一个数独结果 */
		if SCnt == 0 { /* 首次得到结果 */
			for tc = 0; tc <= Length; tc++ {
				Mem2[tc] = Mem1[tc]
			}
			Mem = &Mem2 /* 将下一次计算的结果写到Mem2中 */
		}
		SCnt++ /* 这里第一种解决方案得到后，返回继续 选行 来看有没有第二种解决方案 */
		return
	}

	// fmt.Println(k) /* 打印每次查找的行 */
	/* 从头结点开始一直向右 直到回到头结点
	   挑选结点数量最小的那一行，如果数量小于等于1直接用这行 */
	for t = Head.right; t != &Head; t = t.right {
		if Cnt[t.c] < min {
			min = Cnt[t.c]
			tc = t.c
			if min <= 1 {
				break
			}
		}
	}
	/* min==0的时候会把列删除然后再把列恢复然后返回，说明之前选错了行导致出现了结点为0的列，重新往下选择一行。 */
	Remove(tc) /* 移除这一列 */
	/* 扫描这一列 直到 回到列结点 */
	for t = Col[tc].down; t != &Col[tc]; t = t.down {
		Mem[k] = t.r /* mem[k]存储t的行数，最后可以通过行数来推断数独的几行几列填入了哪个数字 */

		/* 如果没有这一步的话，在下面for循环的过程中会陷入死循环 */
		t.left.right = t /* 经检查这两个指针所指向的地址不同 */

		/* 开始访问t的右边 直到回到t。但是由于t在remove(tc)的过程中左右被跳过，所以tt!=t可能会一直成立，所以需要上一步来保证能回到t */
		for tt = t.right; tt != t; tt = tt.right {
			Remove(tt.c) /* 移除该行中所有带结点的列 */
		}

		/* 等到该行的所有结点都删除以后，把t结点彻底地删除 */
		t.left.right = t.right

		Solve(k + 1)   /* 给下一个找行 */
		if SCnt >= 2 { /* 这里找到2个解就退出 */
			return
		}

		/* 同上，避免死循环 */
		t.right.left = t

		/* 恢复所有被删除的列 */
		for tt = t.left; tt != t; tt = tt.left {
			Resume(tt.c)
		}

		t.right.left = t.left /* 恢复t结点 */
	}
	Resume(tc) /* 恢复tc列,一旦跑出来了说明之前选错了行，且如果一直回溯到一开始然后没有更多的行可以选择且sCnt为0就说明没有解决方案 */
}

/*PrintSudoku
* 打印数独
* 这里需要win32api
* 将计算得到的数据上不同颜色
**/
func PrintSudoku(res int) {
	var (
		i, tmp int
		ans    [Length]int
		mem    = &Mem1
	)
	if res == 2 { /* 确定打印那个结果 */
		mem = &Mem2
	}

	for i = 1; i <= Length; i++ {
		ans[mem[i]/9%Length] = mem[i]%9 + 1
	}

	fmt.Println(" ---------+---------+---------")
	for i = 1; i <= Length; i++ {
		if i%3 == 1 {
			fmt.Print("|")
		}

		if tmp = ans[i-1]; tmp > 0 {
			if SudokuData[i-1] == 0 { /* 该位置是计算得到的,标红色 */
				mSetConsoleTextAttribute(syscall.Stdout, 0x04|0x08)
			}
			fmt.Printf(" %d ", tmp) /* 下面把前景色重置为白色 */
			mSetConsoleTextAttribute(syscall.Stdout, 0x04|0x02|0x01)
		} else {
			fmt.Print(" . ")
		}

		if i < Length {
			if i%27 == 0 {
				fmt.Println("|\n|---------+---------+---------|")
			} else if i%9 == 0 {
				fmt.Println("|\n|         |         |         |")
			}
		}
	}
	fmt.Println("|\n ---------+---------+---------")
}

var setConsoleTextAttribute = syscall.NewLazyDLL("kernel32.dll").NewProc("SetConsoleTextAttribute")

func mSetConsoleTextAttribute(hConsoleOutput syscall.Handle, wAttributes uint16) bool {
	ret, _, _ := syscall.SyscallN(setConsoleTextAttribute.Addr(),
		uintptr(hConsoleOutput),
		uintptr(wAttributes))
	return ret != 0
}
